package 剑指II;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-22
 **/

public class Jz081允许重复选择元素的组合 {

    /**
     * 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，
     * 找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
     * candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 
     * 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
     * <p>
     * 示例 1：
     * 输入: candidates = [2,3,6,7], target = 7
     * 输出: [[7],[2,2,3]]
     * 示例 2：
     * 输入: candidates = [2,3,5], target = 8
     * 输出: [[2,2,2,2],[2,3,3],[3,5]]
     * 示例 3：
     * 输入: candidates = [2], target = 1
     * 输出: []
     * 示例 4：
     * 输入: candidates = [1], target = 1
     * 输出: [[1]]
     * 示例 5：
     * 输入: candidates = [1], target = 2
     * 输出: [[1,1]]
     *  
     * 提示：
     * 1 <= candidates.length <= 30
     * 1 <= candidates[i] <= 200
     * candidate 中的每个元素都是独一无二的。
     * 1 <= target <= 500
     */

    private int[] arr;
    private int target;
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        this.arr = candidates;
        this.target = target;

        this.dfs(0, new ArrayList<>(), 0);

        return this.result;
    }

    private void dfs(int index, List<Integer> path, int sum) {

        if (sum == this.target) {
            this.result.add(new ArrayList<>(path));
            return;
        }

        if (sum > this.target) {
            return;
        }

        if (index == this.arr.length) {
            return;
        }

        for (int i = index; i < this.arr.length; i++) {
            if (sum + this.arr[i] > this.target) {
                continue;
            }
            path.add(this.arr[i]);
            this.dfs(i, path, sum + this.arr[i]);
            path.remove(path.size() - 1);
        }

    }

    public static void main(String[] args) {
        Jz081允许重复选择元素的组合 n = new Jz081允许重复选择元素的组合();
        int[] arr = {2, 3, 6, 7};
        List<List<Integer>> result = n.combinationSum(arr, 7);
        System.out.println(JSON.toJSONString(result));
    }

}
